import java.util.*;

public class Leetcode1609 {

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(1,10,4,3,null,7,9,12,8,6,null,null,2);
        int i = 1;
        TreeNode root = new TreeNode(a.get(0));  // 根节点
        TreeNode current = null;
        Integer value = null;

        //层序创建二叉树
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (i < a.size()) {
            current = queue.poll();//从链表中移除并获取第一个节点
            value = a.get(i++);
            if (value != null) {
                TreeNode left = new TreeNode(value);
                current.left = left;//创建当前节点的左孩子
                queue.offer(left); // 在链表尾部 左孩子入队
            }
            value = a.get(i++);
            if (value != null) {
                TreeNode right = new TreeNode(value);
                current.right = right;//创建当前节点的右孩子
                queue.offer(right);// 在链表尾部 右孩子入队
            }

        }

        System.out.println(isEvenOddTree(root));
    }

    public static boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> treeNodes = new ArrayDeque<>();
        Queue<TreeNode> childTreeNodes = new ArrayDeque<>();
        treeNodes.add(root);
        int currentLevel = 0;

        int currentLevelParentNumber = Integer.MIN_VALUE;
        while (!treeNodes.isEmpty()) {
            TreeNode treeNode = treeNodes.poll();
            if (treeNode != null) {
                childTreeNodes.add(treeNode.left);
                childTreeNodes.add(treeNode.right);

                if (currentLevel % 2 == 0) {
                    if (treeNode.val > currentLevelParentNumber && treeNode.val % 2 == 1) {
                        currentLevelParentNumber = treeNode.val;
                    } else {
                        return false;
                    }
                } else {
                    if (treeNode.val < currentLevelParentNumber && treeNode.val % 2 == 0) {
                        currentLevelParentNumber = treeNode.val;
                    } else {
                        return false;
                    }
                }
            }


            if (treeNodes.isEmpty()) {
                treeNodes.addAll(childTreeNodes);
                childTreeNodes.clear();
                currentLevel++;
                if (currentLevel % 2 == 0) {
                    currentLevelParentNumber = Integer.MIN_VALUE;
                } else {
                    currentLevelParentNumber = Integer.MAX_VALUE;
                }
            }
        }

        return true;
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
